#pragma once
#include "common.h"
int PartSort(vector<int>& nums, int l, int r, int k) {
    int i = l + 1, j = r;
    int val = nums[k];
    swap(nums[l], nums[k]);
    while (true) {
        while (i <= j && nums[i] < val) {
            ++i;
        }
        while (i <= j && nums[j] > val) {
            --j;
        }
        if (i > j) {
            break;
        }
        swap(nums[i], nums[j]);
        ++i, --j;
    }
    swap(nums[l], nums[j]);
    return j;
}


void _QuickSort(vector<int>& nums, int l, int r) {
    if (l >= r) {
        return;
    }
    int k = l + rand() % (r - l + 1);
    int pos = PartSort(nums, l, r, k);
    _QuickSort(nums, l, pos - 1);
    _QuickSort(nums, pos + 1, r);
}


void QuickSort(vector<int>& nums) {
    srand(time(nullptr));
    _QuickSort(nums, 0, nums.size() - 1);
}